package com.hy.study.tree;

/**
 * 以数组的方式实现顺序存储二叉树
 */
public class ArrBinaryDemo {
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        //根节点的下标为0
        // 将数组进行前序遍历
        arrBinaryTree.perOrder();
        System.out.println();
        arrBinaryTree.infixOrder();
        System.out.println();
        arrBinaryTree.postOrder();
    }


}

class ArrBinaryTree {
    private int[] arr;//存储数据节点的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    /**
     * 前序遍历 将树转换成数组
     *
     * @param index 表示数组的下标
     */
    public void preOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历");
            return;
        }
        //输出当前元素
        System.out.printf(arr[index] + "\t");
        //向左递归遍历
        int leftIndex = (index * 2) + 1;
        if (leftIndex < arr.length) {
            preOrder(leftIndex);
        }
        //向右递归遍历
        int rightIndex = (index * 2) + 2;
        if (rightIndex < arr.length) {
            preOrder(rightIndex);
        }
    }

    public void perOrder() {
        this.preOrder(0);
    }

    public void infixOrder() {
        this.infixOrder(0);
    }

    public void postOrder() {
        this.postOrder(0);
    }

    /**
     * 数组的中序遍历
     */
    public void infixOrder(int index) {
        int arrLength = arr.length;
        int leftIndex = (2 * index) + 1;
        int rightIndex = (2 * index) + 2;
        if (leftIndex < arrLength) {
            infixOrder(leftIndex);
        }
        System.out.printf(arr[index] + "\t");
        if (rightIndex < arrLength) {
            infixOrder(rightIndex);
        }
    }

    public void postOrder(int index) {
        int maxArr = arr.length;
        int leftIndex = (2 * index) + 1;
        int rightIndex = (2 * index) + 2;
        if (leftIndex < maxArr) {
            postOrder(leftIndex);
        }
        if (rightIndex < maxArr) {
            postOrder(rightIndex);
        }
        System.out.printf(arr[index] + "\t");
    }


}
